package site.wanjiahao.union;

/**
 * 并查集抽象类
 */
public abstract class UnionFind {

    // 存储父元素集合
    int[] parents;

    public UnionFind(int capacity) {
        checkCapacity(capacity);
        // 初始化，父元素集合, 自己指向自己
        parents = new int[capacity];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    private void checkCapacity(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity is null");
        }
    }

    protected void checkRange(int index) {
        if (index >= parents.length) {
            throw new IllegalArgumentException("index is Illegal Argument");
        }
    }

    /**
     * 查找该元素所属的父节点
     * @param v
     * @return
     */
    public abstract int find(int v);

    /**
     * 合并v1, v2集合
     * @param v1
     * @param v2
     */
    public abstract void union(int v1, int v2);

    /**
     * 检查v1, v2是否属于同一个集合
     */
    public boolean isSame(int v1, int v2) {
        return find(v1) == find(v2);
    }
}
